package com.leet.code.lcof;

import com.algorithm.model.TreeNode;
import com.algorithm.model.TreeNodeService;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Code34 {

    public static void main(String[] args) {
//        int[] s = {5, 4, 8, 11, 11, 13, 4, 7, 2, 7, 2, 5, 1, 5, 1};
//        int[] s = {1, 2, 2};
//        int[] s = {1};
        int[] s = {-2, -3, -3};
        TreeNode root = TreeNodeService.getTreeByArray(s);

        Code32 code32 = new Code32();
        for (int i : code32.levelOrder(root)) {
            System.out.print(i + ",");
        }
        System.out.print("\b");
        System.out.println();


        Code34 c = new Code34();
        c.pathSum(root, -5);

        System.out.println(c.result);

    }

    int sum;
    LinkedList<Integer> list;
    List<List<Integer>> result = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) return result;
        this.sum = sum;
        list = new LinkedList<>();
        check(root, 0);
        return result;
    }

    public void check(TreeNode treeNode, int s) {
        if (treeNode == null) {
            return;
        }

        s = s + treeNode.val;
        if (s == sum && treeNode.left == null && treeNode.right == null) {
            list.add(treeNode.val);
            List<Integer> l1 = new ArrayList<>(list.size());
            for (Integer i : list) {
                l1.add(i);
            }
            result.add(l1);
            list.removeLast();
            return;
        }


//        if (s < sum) {
        list.add(treeNode.val);
        check(treeNode.left, s);
        check(treeNode.right, s);
        list.removeLast();
//        }


    }

}
